/*splay
基本操作：splay(x)将x旋转到根
Zig Step 根节点
Zig-Zig Step
同为左儿子/右儿子
依次右/左旋
Zig-Zag Step
p左x右，x左旋再右旋
p右x左，x右旋再左旋

插入splay一次即可

删除时，先splay到根，
若只有一个儿子，直接删除
否则找左子树最大的一项代替之
并将该项的左儿子代替它的父亲

分离，如将[1,3]与[4,7]分离，
可以先将3splay至根节点，
之后分离3与原先的根节点

合并，前提为左边权值均小于右边

*/

void rotate(int x)
{
    int y=dad[x],z=dad[y];
    bool f=s[1][y]==x;
    if(!is_root(y))s[s[1][z]==y][z]=x;
    s[f][y]=s[!f][x];s[!f][x]=y;
    dad[x]=z;dad[y]=x;dad[s[f][y]]=y;
    update(x);update(y);
}

//双旋
for(;!is_root(x);rotate(x))
	if(!is_root(dad[x]))
    	s[0][dad[x]]==x^s[0][dad[dad[x]]]==dad[x]?
			rotate(x):rotate(dad[x]);

int find_max(int cur)
{
	for(;s[1][cur];cur=s[1][cur]);
	return cur;
}
void combine(int cur,cur1)  //合并
{
	x=find_max(cur);
	splay(cur);
	rs[cur]=cur1;
}
